Dispersion of data is a common problem in many fields, including image processing. In image processing, data fails to converge to one grouping for numerous reasons, such as, imperfections in the imaging environment, the algorithm(s) employed, and/or the discrete nature of processing the data using a computer. Data dispersion detrimentally affects some types of image processing more than others. For instance, finding lines in images is more detrimentally effected by dispersion than finding regions. Typically, the integrity of smaller groupings of data, such as lines, relative to the remainder of the image, suffer more from dispersion effects. It is also difficult to identify elements composed of a relatively small amount of data because of confusing appropriate data with superfluous data.
An example of dispersion of edge points of a line is illustrated using FIG. 1, not drawn to scale, which depicts an imaged line 102 having multiple edge-point directions 100, shown schematically. An edge point is derived from underlying image pixels, where an image pixel is a picture element characterized by a grey value, where an image can be represented as an array of image pixels. A plurality of connected edge points creates a contour, such as a line or boundary 200 between two regions 202 and 204, illustrated in FIG. 2. The direction of an edge point 210 is perpendicular to the line 200 upon which the edge point 208 resides. Turning back to FIG. 1, the edge points 110 of the line 102 do not share a common direction 100, but are distributed about a peak angle, as shown in the discrete-angle histogram 104. The edge-point directions 100 fall into multiple discrete bins 108 that are distributed around a peak bin 106, where the peak bin 106 represents the mode of the histogram (i.e. the primary direction of the edge points 110 in the line 102). The lack of convergence of all the edge points 110 to the peak bin 106 illustrates the typical data dispersion present for lines in images. Lines detected using the Hough line-transform method also suffer from this problem.
The majority of line finding algorithms in machine-vision applications, are variations of the Hough line-transform method, described in U.S. Pat. No. 3,069,654. The Hough line-transform method transforms characteristics of edge points into line characteristics, and represents the line characteristics on a Hough space, where a point in the Hough space represents a line.
The characteristics of the edge points include the edge-point position, denoted (x, y), edge-point direction, denoted θ, and optionally, edge-point magnitude, denoted M, which are all measured in Cartesian space. The edge-point position is typically a function of the position of a neighborhood of the underlying image pixels. The edge-point magnitude and direction are a function of the change in grey value of the image pixels that contribute to the edge point.
The characteristics of an edge point, (θ, x, y, and optionally M) are transformed into line characteristics (d, c, and α) Typically, the characteristics of edge points in a contour are called features (such as position), while characteristics derived from the features are called parameters (such as line angle).
The line characteristics are illustrated in Cartesian space in FIG. 3. The line characteristics include a line angle 302, denoted α, which is the angle of the line 300 from the horizontal, a distance-vector 304, denoted d, which is the shortest distance from the origin of a coordinate system 314 to the line 300, and, optionally, a collinear distance 306, denoted c, which is the distance from the edge point 308 to the place where d touches the line 300, in Cartesian space. d is signed to differentiate between lines with identical α and d parameters on opposite sides of the origin 314. More specifically, the sign of d is negative if the angle 312 of d from the horizontal in Cartesian coordinates is less than 180° and greater than, or equal to, zero (i.e., 180°>β≧0); and positive when the angle 312 of d is less than 360°, and greater than, or equal to, 180° (i.e., 360°>β≧180°).
d, c, and α are generated from the following Hough-transform equations:d=x·sin(θ)−y·cos(θ)  [1]c=x·cos(θ)+y·sin(θ)  [2]αdegrees=[θ+90]mod180  [3]d and α are stored on a Hough space.
FIG. 4A depicts an instance of a Hough space 400 for lines. The Hough space for lines is a two-dimensional space in which lines from an image are recorded. The Hough space is adequately represented as a two-dimensional array of bins 402. One axis 404 represents the line-angle, α, and the other axis 406 represents the distance vectors, d. A point on a Hough space represents a line.
During the transformation, for each edge point in an input image: the values of d and α are calculated, and the bin of the Hough space, whose range includes the value of d and α for each edge point, is incremented. Once all the edge points in the input image have been examined, the Hough space is searched for maximum values, using peak detection, a method known in the art. The bin having the highest value in the Hough space represents the strongest line detected in the input image, the second highest local maxima represents the second strongest line detected, and so forth.
Each bin 402 in the Hough space represents a discrete range of angles and a discrete range of distance vectors. FIG. 5 shows an instance of a quantization of the angles for a Hough space, where 360° is divided into 64 bins. Each of the 64 bins has a range of 5.62 degrees per bin, where the first bin accommodates the angles within 0-5.62°, the second bin accommodates the angles within 5.62°-11.24°, and so on.
Typically, the line-angle range and/or distance-vector range for each bin in the Hough space, and the divisions of ranges between the bins, are driven by system and application parameters, and often do not exactly represent the line angles or distance vectors in a given. image. Thus, the partitioning of the line angle and: the distance vector into discrete bins hinders detecting lines whose edge points straddle the boundaries, such as lines with a line angle of 5.62°, in the above example. The edge points of such lines, typically, transform into more than one bin, thus, it is more difficult to detect these lines, as is further discussed in J. Brian Burns, Allen R. Hanson, and Edward M. Riseman, “Extracting Straight Lines”, IEEE Transactions on Pattern Analysis and Machine Intelligence, 8(4), 1986.
The effects of dispersion and the number of partitions in an axis are decreased by increasing the range of data accepted in each bin. However, increasing the range decreases precision of the line angles and/or distance vectors. As illustrated using FIG. 6, which depicts a 59° line 600 and a 51° line 610 and their respective discrete-angle histograms 602 and 612 derived from a Hough space. A Hough space created using a four-bit representation for angle partitions the line-angle axis of the Hough space so that the edge points 604 and 614 of both lines 600 and 610 all map to bin two in the Hough space. Thus, the ability is lost to distinguish between a 51° line and 59° line in Hough space.
Other techniques known in the art, such as a Point Spread Function update method, for example, also decrease dispersion effects. For each edge point, the Point Spread Function update method increments more than one bin with a partial weighting. Although the edge points do not contribute 100% to the weight of the appropriate bin, it is less likely any edge points fail completely to contribute to the weight of the appropriate bin. Although the Point Spread Function update method compensates, in part, for dispersion, it also causes a loss of precision because the Point Spread Function tends to smear the Hough space peaks.
An additional problem with image processing smaller contours is the inability to identify appropriate groupings of edge points of each contour given the superfluous noise and background clutter. The paper W. Eric L. Grimson and Daniel P. Huttenlocher “On the Sensitivity of the Hough Transform for Object Recognition,” Transactions on Pattern Analysis and Machine Intelligence, 12(3), 1990, discusses how line finding and object detection using Hough transforms suffers from superfluous noise and background clutter, particularly when trying to detect shorter lines.
Also, the Hough transform is only as precise as the underlying edge-point data, which is limited according to current technology. Further, the precision cannot be greatly increased by interpolating the edge-point data to a higher number of bits because, eventually, the interpolated bits do not represent meaningful precision.